//
// Created by francklinson on 2021/7/11 AT 22:35.
//

//在给定的网格中，每个单元格可以有以下三个值之一：
//值0代表空单元格；
//值1代表新鲜橘子；
//值2代表腐烂的橘子。
//每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
//
//返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/rotting-oranges
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * bfs 记录层数
     * @param grid
     * @return
     */
    int orangesRotting(vector<vector<int>> &grid) {
        queue<pair<int, int>> q;
        unsigned int m = grid.size(), n = grid[0].size();
        int numFreshOrange = 0;
        // 遍历一次，将最初的烂橘子加入队列
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    q.emplace(i, j);
                    grid[i][j] = 0;
                } else if (grid[i][j] == 1) ++numFreshOrange;
            }
        }
        if (numFreshOrange == 0) return 0; // 没有新鲜橘子
        vector<pair<int, int>> movements{{1,  0},
                                         {-1, 0},
                                         {0,  1},
                                         {0,  -1}};
        int passedTime = -1;
        while (!q.empty()) {
            ++passedTime;
            unsigned int levelSize = q.size(); // 这一层的数量
            for (int i = 0; i < levelSize; ++i) {
                auto p = q.front();
                q.pop();
                for (int j = 0; j < 4; ++j) {
                    int nextI = p.first + movements[j].first;
                    int nextJ = p.second + movements[j].second;
                    // 烂橘子四周的新鲜橘子
                    if (nextI >= 0 and nextI < m and nextJ >= 0 and nextJ < n and grid[nextI][nextJ] == 1) {
                        q.emplace(nextI, nextJ);
                        grid[nextI][nextJ] = 0; // 清空橘子
                        --numFreshOrange; // 新鲜橘子变烂
                    }
                }
            }
        }
        return numFreshOrange == 0 ? passedTime : -1;
    }
};

int main() {
    vector<vector<int>> grid{{2, 1, 1},
                             {0, 1, 1},
                             {1, 0, 1}};
    Solution sol;
    cout << sol.orangesRotting(grid) << endl;
    return 0;
}

